package com.lfg.leetcode.leetcode300;


public class No329longestIncreasingPath {
    public static void main(String[] args) {
        System.out.println(longestIncreasingPath(new int[][]{
                new int[]{3, 4, 5},
                new int[]{3, 2, 6},
                new int[]{2, 2, 1}
        }));
    }

    public static int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int cnt = 0;
        Integer[][] data = new Integer[matrix.length][matrix[0].length];
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                cnt = Math.max(dfs(matrix, i, j, visited, null, data), cnt);
            }
        }
        return cnt;
    }

    public static int dfs(int[][] matrix, int i, int j, boolean[][] visited, Integer val, Integer[][] data) {
        if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[i].length) {
            return 0;
        }
        if ((null != val && matrix[i][j] <= val) || visited[i][j]) {
            return 0;
        }
        Integer value = data[i][j];
        if (null != value) {
            return value;
        }
        visited[i][j] = true;
        int ret1 = dfs(matrix, i + 1, j, visited, matrix[i][j], data);
        int ret2 = dfs(matrix, i - 1, j, visited, matrix[i][j], data);
        int ret3 = dfs(matrix, i, j + 1, visited, matrix[i][j], data);
        int ret4 = dfs(matrix, i, j - 1, visited, matrix[i][j], data);
        int ret = Math.max(Math.max(ret1, ret2), Math.max(ret3, ret4));
        visited[i][j] = false;
        data[i][j] = ret + 1;
        return ret + 1;
    }

}



